This invention relates to an error correction circuit for correcting bit errors in a codeword which is either received or reproduced from a digital signal as a received codeword.
It is already known in correcting bit errors to use a Euclidean algorithm of error correction with addition, multiplication, and division carried out on a finite field GF(2.sup.m), where m represents an integer equal to one or greater. Based on the results of the Euclidean algorithm, it is possible to calculate an error location polynomial and an error value polynomial. An example is disclosed in Japanese Patent Prepublication (A) No. 101,742 of 1989.
In each of the successive stages of the Euclidean algorithm, a dividing circuit is used in dividing a dividend polynomial by a divisor polynomial, namely, a higher degree polynomial by a lower degree polynomial to provide a remainder polynomial of a degree which is herein referred to as a remainder degree. The higher and the lower degree polynomials have a degree difference which is equal to at least to one.
Preferably, the dividing circuit is the circuit disclosed in the specification of U.S. patent application Ser. No. 08/186,574 (pending) filed Jan. 26, 1994, by the present inventor. The application will herein be incorporated by reference.
The received codeword may include the bit errors of an error number, or the number of errors, this number is either less than a maximum number of correctable errors or not less than the maximum number. When the remainder degree is less than the maximum number, the remainder polynomial is said to satisfy a condition for error correction. Otherwise, the remainder polynomial does not satisfy the condition for error correction. The Euclidean algorithm is carried out consecutively in stages until an eventual remainder polynomial satisfies the condition.
The maximum number of correctable errors will now be denoted by t. A syndrome polynomial S(X) is derived from the received codeword in the manner known in the art. In the syndrome polynomial, coefficients of powers of X are represented by powers of a primitive element .alpha.. Merely for convenience and clarity of print, such powers of the primitive element will herein be denoted by A(a) with its index treated as if an argument. The index is variable between zero and (2.sup.t -2), both inclusive. Incidentally, A(2.sup.t -1)=A(O)=1. In an initial or first stage of the Euclidean algorithm, X.sup.2t is used as the dividend or the higher degree polynomial with the syndrome polynomial used as the divisor or the lower degree polynomial.
When the maximum number of correctable errors is equal to four, the syndrome polynomial may be: EQU S(X)=A(a)X.sup.7 +A(b)X.sup.6 +. . .+A(c)X+A(d),
where each of a, b, c, and d represents one of zero through 254. At least one of the coefficients A(b), . . . , and A(c) is not equal to zero. In this event, the remainder polynomial would be, in the first stage of the Euclidean algorithm a six-degree polynomial and is herein called a first remainder polynomial. In a second stage of the Euclidean algorithm, the syndrome polynomial is used as the higher degree polynomial with the first remainder polynomial used as the lower degree polynomial. The division would provide a five-degree polynomial as a second remainder polynomial. In a third stage, the first remainder polynomial is used as the higher degree polynomial with the second remainder polynomial used as the lower degree polynomial to provide a four-degree polynomial as a third remainder polynomial. In a fourth stage, the second remainder polynomial is used as the higher degree polynomial with the third remainder polynomial used as the lower degree polynomial to provide a three-degree polynomial as a fourth remainder polynomial. Now the remainder degree is less than the maximum number of correctable errors. In this case fourth remainder polynomial satisfies the condition for error correction. It becomes possible to calculate error locations and error patterns and to correct the bit errors.
In a conventional error correcting circuit, the dividing circuit has been put in operation in each stage of the Euclidean algorithm assuming that the degree difference is equal to one. This assumption is not always correct. In other words, the degree difference may be two or more. Such a case has not been studied in the prior art. As a consequence, misoperation has been unavoidable. It has been inevitable with the conventional error correcting circuit to erroneously calculate the error location polynomial and the error value polynomial to erroneously correct the bit errors incorrectly.
In addition, the received codeword may include the bit errors of an error number which is greater than the maximum number of correctable errors. In such an event, the conventional error correcting circuit judges the inability of correcting the bit errors to produce a flag which indicates that the received codeword should be dealt with by a different circuit. The conventional error correcting circuit is, however, capable of proceeding with the Euclidean algorithm to eventually erroneously produce the condition for error correction. As a result, the error location polynomial and the error value polynomial have been erroneously calculated with the conventional error correcting circuit to carry out miscorrection of the bit errors.